
class TreeNode {
    constructor(item,left=null,right=null){
        this.item = item ;
        this.left = left ;
        this.right = right ;
    }
}

let root = new TreeNode( 1 );
root.left = new TreeNode( 2 );
root.right = new TreeNode( 3 );

function inorder( root ){
    let output = [];

    let traverse = function( node ) {
        if( node ) {
            traverse( node.left );
            output.push( node.item );
            traverse( node.right );
        }
    }

    traverse( root );
    return output;
}

// 中序遍历被破坏后的二叉树
console.log( inorder( root ) );

function swap(node,child){
    let temp = node.item;
    node.item = child.item ;
    child.item = temp ;
}

function recover( node ) {
    if( node ) {
        
        let left = node.left ;
        recover(left);

        let right = node.right ;
        if( right && right.item < node.item ) {
            swap( node , right );
        }
        if( left && left.item > node.item ) {
            swap( node , left );
        }
        if( right && right.item < node.item ) {
            swap( node , right );
        }
        
        recover(right);
    }
}

// 恢复二叉树
recover( root );

// 中序遍历恢复后的二叉树
console.log( inorder( root ) );
